package search;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {2, 2, 2, 4, 6, 7, 7, 7, 9, 22, 72, 89};
        //int[] arr = {2,4,8,9,16,202,1101};

        Scanner scanner = new Scanner(System.in);
        int value = scanner.nextInt();
        //int ret = binarySearchRecursion(arr, 0, arr.length - 1, value);
        List<Integer> list = binarySearchRecursion2(arr, 0, arr.length - 1, value);
        System.out.println(list.toString());

        //System.out.println(ret);
    }

    public static int binarySearch(int[] arr, int left, int right, int value) {

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < value) {
                left = mid + 1;
            } else if (arr[mid] > value) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    public static int binarySearchRecursion(int[] arr, int left, int right, int value) {

        System.out.println("hh");
        int mid = left + (right - left) / 2;
        if (left > right) {
            return -1;
        }
        if (arr[mid] > value) {
            return binarySearchRecursion(arr, left, mid - 1, value);
        } else if (arr[mid] < value) {
            return binarySearchRecursion(arr, mid + 1, right, value);
        } else {
            return mid;
        }
    }

    //二分查找arr中所有的值，上面两种只能查找一个
    public static List<Integer> binarySearchRecursion2(int[] arr, int left, int right, int value) {
        int mid = left + (right - left) / 2;
        if (left > right) {
            return new ArrayList<Integer>();
        }
        if (arr[mid] > value) {
            return binarySearchRecursion2(arr, left, mid - 1, value);
        } else if (arr[mid] < value) {
            return binarySearchRecursion2(arr, mid + 1, right, value);
        } else {
            List<Integer> resIndexList = new ArrayList<Integer>();
            int temp = mid - 1;
            while (true) {
                if (temp < 0 || arr[temp] != value) {
                    break;
                }
                resIndexList.add(temp);
                temp--;
            }
            resIndexList.add(mid);
            temp = mid + 1;
            while (true) {
                if (temp > arr.length - 1 || arr[temp] != value) {
                    break;
                }
                resIndexList.add(temp);
                temp++;
            }
            return resIndexList;
        }
    }

}
